package com.example.leetcode.dp;

import com.example.leetcode.dp.common.DPUtils;

class Solution64 {
    public int minPathSum(int[][] grid) {
        // grid 元素为非负整数
        // 递归会超时, 应该使用DP
//        return DFSUtils.minPathSum(grid);
//        return DPUtils.minPathSum(grid);
        return DPUtils.minPathSumPro(grid);
    }
}

public class leetcode64 {
    public static void main(String[] args) {
        Solution64 solution64 = new Solution64();
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int[][] grid1 = {{1, 2, 3}, {4, 5, 6}};
        System.out.println(solution64.minPathSum(grid));
        System.out.println(solution64.minPathSum(grid1));
    }

}
